package tree

import "reflect"

// 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
// 分治法(可用于二叉树)：因为参数节点可能都在左边，也可能都在右边，所以如果有左右子树的公共祖先，就返回子树的祖先，否则返回根节点

func LowestCommonAncestor(root, p, q *Node) *Node {
	// check
	if root == nil {
		return root
	}

	if reflect.DeepEqual(root, p) || reflect.DeepEqual(root, q) {
		return root
	}

	//if root == p || root == q {
	//	return root
	//}

	//divide
	left := LowestCommonAncestor(root.Left, p, q)
	right := LowestCommonAncestor(root.Right, p, q)

	//conquer
	if left != nil && right != nil {
		return root //左子树和右子树都有公共节点，则为根节点
	}

	if left != nil {
		return left //只存在于左子树，则返回左子树的节点
	}
	if right != nil {
		return right //只存在于右子树，则返回右子树的节点
	}
	return nil
}

//两次遍历方法：
//注意到题目中给出的是一棵「二叉搜索树」，因此我们可以快速地找出树中的某个节点以及从根节点到该节点的路径，例如我们需要找到节点 pp：
//
//我们从根节点开始遍历；
//如果当前节点就是 p，那么成功地找到了节点；
//如果当前节点的值大于 p 的值，说明 p 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
//如果当前节点的值小于 p 的值，说明 p 应该在当前节点的右子树，因此将当前节点移动到它的右子节点。
//
//对于节点 q 同理。在寻找节点的过程中，我们可以顺便记录经过的节点，这样就得到了从根节点到被寻找节点的路径。
//
//当我们分别得到了从根节点到 p 和 q 的路径之后，我们就可以很方便地找到它们的最近公共祖先了。
//显然，p和 q的最近公共祖先就是从根节点到它们路径上的「分岔点」，也就是最后一个相同的节点。因此，如果我们设从根节点到 p 的路径为数组 path_p，从根节点到 q 的路径为数组 path_q，那么只要找出最大的编号 i，其满足
//path_p[i]=path_q[i]
//那么对应的节点就是「分岔点」，即 p 和 q 的最近公共祖先就是 path_p[i]（或 path_q[i]）
// 时间复杂度和空间复杂度为O(n),与p和q在树中的深度线性相关
func getPath(root, target *Node) (path []*Node) {
	node := root
	for !reflect.DeepEqual(node, target) {
		path = append(path, node)
		if target.Val < node.Val {
			node = node.Left
		} else {
			node = node.Right
		}
	}
	path = append(path, node)
	return
}

func LowestCommonAncestor2(root, p, q *Node) (ancestor *Node) {
	pathP := getPath(root, p)
	pathQ := getPath(root, q)
	//寻找分叉点
	for i := 0; i < len(pathP) && i < len(pathQ) && pathP[i] == pathQ[i]; i++ {
		ancestor = pathP[i]
	}
	return
}

//一次遍历法：
//整体的遍历过程与方法一中的类似：
//我们从根节点开始遍历；
//如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
//如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
//如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，pp 和 qq 要么在当前节点的不同的子树中，要么其中一个就是当前节点。
//时间复杂度 O(n)
//空间复杂度O(1)
func LowestCommonAncestor3(root, p, q *Node) (ancestor *Node) {
	ancestor = root
	for {
		if p.Val < ancestor.Val && q.Val < ancestor.Val {
			if ancestor.Left != nil {
				ancestor = ancestor.Left
			}

		} else if p.Val > ancestor.Val && q.Val > ancestor.Val {
			if ancestor.Right != nil {
				ancestor = ancestor.Right
			}

		} else {
			return
		}
	}
}
